package DataStructure.java;

public class KMP {
    public static void main(String[] args) {
        String s = "abacababc";
        String p = "abab";
        System.out.println(KMPSearch(s,p));
    }

    static int KMPSearch(String s, String p){
        int i = 0, j = 0, m = s.length(), n = p.length();
        int[] next = getNext(p);
        while (i < m && j < n){
            if (j == -1 || s.charAt(i) == p.charAt(j)){
                ++i;
                ++j;
            } else {
                j = next[j];
            }
        }
        if (j == n)
            return i-j;
        else
            return -1;
    }

    static int[] getNext(String s){
        int n = s.length();
        int[] next = new int[n]; // 除此字符之外的前缀后缀最长公共元素长度
        next[0] = -1;
        int k = -1, j = 0; //s[k]表示前缀，s[j]表示后缀
        while (j < n-1) {
            if (k == -1 || s.charAt(j) == s.charAt(k)) {
                ++j;
                ++k;
                if (s.charAt(j) != s.charAt(k))
                    next[j] = k;
                else // 如果字母相同，就继续递归
                    next[j] = next[k];
            } else {
                k = next[k];
            }
        }
        return next;
    }
}

